Math'φsics

Menu
  • Acceuil
  • Maths
  • Physique
    • Maths
    • Physique
  • Entropie d'une source

    Formulaire de report


    Entropie \(H(X)\) d'une source \(X\)
    Quantité définie par l'Espérance de l'Information élémentaire détenue par les différentes réalisations d'une Variable aléatoire : $$H(X)={\Bbb E}[-\log_2(p_X(x))]=-\sum_{x\in\mathcal X}p_X(x)\log_2(p_X(x))$$
    • cette quantité est exprimée en bits
    • on prend la convention \(0\log_2(0)=0\) pour faire en sortequ'un événement impossible n'intervienne pas dans la somme
    • interprétation : correspond au degré d'incertitude (surprise) pour le destinataire
      •     
    • permet aussi de représenter le nombre de questions nécessaires pour identifier qqch : chaque classe est associée à un message dont la longueur est donnée par son Information élémentaire, et chaque question permet de déchiffrer un caractère du message
      •         
    • dans ce cas, la meilleure stratégie pour trouver le plus rapidement possible la classe est de maximiser l'entropie pour se rapprocher d'une loi uniforme, et minimiser l'Information élémentaire maximale
    • si \(X\) suit une Loi de Bernoulli de paramètre \(p\), on notera son entropie \(h(p)\)
    • on a \(H(X)=0\iff\) \(X\) est déterministe
    • \(H(X)\) est maximale si \(X\) suit une Loi uniforme
      •     
    • on a alors \(H(X)=\) \(\log_2(\lvert\mathcal X\rvert)\)
    • pour \(\varphi:\mathcal X\to\mathcal Y\), on a \(H(\varphi(X))\leqslant H(X)\), avec égalité si et seulement si \(\varphi\) est injective
    • interprétation en codage source : correspond au nombre asymptotique moyen de bits qu'il faut envoyer par symbole (Premier théorème de Shannon)


    Questions de cours

    Montrer que \(H(X)\leqslant\log_2(\lvert X\rvert)\), avec égalité si et seulement si \(X\) suit une loi uniforme.

    Comparer une distribution quelconque avec la distribution uniforme via la Divergence de Kullback-Leibler, où on fait apparaître \(H(X)\).

    Utiliser l'Inégalité de Gibbs pour conclure.


    Montrer que pour \(\varphi:\mathcal X\to\mathcal Y\), on a \(H(\varphi(X))\leqslant H(X)\), avec égalité si et seulement si \(\varphi\) est injective.

    Développer \(H(X,\phi(X))\) des deux façons différentes.

    On a une composante nulle et une composante positive, ce qui induit une majoration.

    On a égalité si et seulement si la composante positive est nulle : il suffit de voir ce qu'elle représente.


    START
    Ω Basique (+inversé optionnel)
    Recto: Ecrire la dérivée de \(p\mapsto\log_2(p)\).
    Verso: $$\log_2^\prime(p)=\frac1{p\ln(2)}$$
    Bonus:
    Carte inversée ?:
    END
    START
    Ω Basique (+inversé optionnel)
    Recto: Ecrire la dérivée de \(p\mapsto h(p)\).
    Verso: $$\begin{align} h^\prime(p)&=\log_2\left(\frac{1-p}p\right)\\ &=\log_2\left(\frac1p-1\right)\end{align}$$
    Bonus: Le maximum de \(h\) est donc atteint pour \(p=\frac12\), et vaut \(1\).
    Carte inversée ?:
    END

    Exercices

    Calculer l'entropie de la phrase ENSPARISSACLAY.

    On extrapole les probabilités d'apparition à partir du message (⚠ on n'utilise pas la loi uniforme ⚠)

    A partir des probabilités, on utilise la formule du cours et les propriétés du logarithme pour faire le calcul.


    On considère deux joueurs de même niveau qui jouent à un jeu où le vainqueur est le premier qui remporte 4 parties. On note \(N\) la variable aléatoire représentant le nombre de parties jouées jusqu'à une victoire.
    Calculer \(H(N)\).

    Calculer la probabilité que \(N\) prenne chacune des valeurs possibles, en sachant que la dernière partie est toujours une victoire (les parties précédentes peuvent être modélisées via une loi binomiale).

    Calculer l'entropie via la formule du cours.


    On considère une source \(X\) sur un alphabet \(\mathcal X=\{0,1,\dots,9,a,b,\dots,z\}\), avec \(1/3\) de chances de tirer un chiffre, \(1/3\) de chances de tirer une voyelle et \(1/3\) de chances de tirer une consonne. Tous les chiffres sont supposés équiprobables, ainsi que toutes les voyelles et toutes les consonnes. Calculer l'entropie de la source \(X\).

    Cette source peut être partagée en trois via une formule, ce qui rend le calcul plus simple.


    On considère 12 boules dont l'une est soit plus légère, soit plus lourde que les autres. On considère une balance qui permet de fournir les informations suivantes :
    1. Le plateau de gauche est plus lourd.
    2. Les deux plateaux font le même poids.
    3. Le plateau de droite est plus lourd.

    Concevoir une stratégie permettant, en un minimum de pesées, de savoir quelle boule a un poids différent des autres ET si elle est plus lourde ou plus légère.

    Compter le nombre d'issues possibles en tout.
    Il y a 24 issues possibles, chacune correspondant à une certaine boule étant plus légère ou plus lourde.

    Obtenir le nombre de pesées via le \(\log\) dont la base est le nombre d'issues différentes à chaque expérience.
    A chaque expérience, il y a trois issues possibles.
    \(\log_3(24)\approx2.89\), donc la stratégie optimale contient trois pesées seulement.

    La stratégie optimale consiste à se rapprocher au maximum d'une loi uniforme à chaque expérience (maximiser l'entropie), afin d'avoir à faire un nombre minimal de pesées, même dans le pire des cas.


    On considère deux variables aléatoires \(X\) et \(Y\) respectivement sur un alphabet \(\mathcal X\) et \(\mathcal Y\).
    On suppose les deux alphabets disjoints.
    On considère \(\alpha\in[0,1]\) et la variable aléatoire \(Z\) définie par : $$Z=\begin{cases} X\text{ avec probabilité }\alpha\\ Y\text{ avec probabilité }1-\alpha\end{cases}$$
    Calculer \(H(Z)\) en fonction de \(H(X)\) et \(H(Y)\).

    On pose une v.a. Intermédiaire qui permet de connaître le mode de \(Z\).

    On utilise la formule qui lie entropie conjointe et entropie conditionnelle, en sachant qu'une entropie conditionnelle s'annule.

    On utilise la formule de décomposition de l'entropie conditionnelle pour conclure.



    'information